class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        acc = [0]*10
        ret = []
        def traverse(begin, left):
            if left==0:
                hour = 0
                for i in range(4):
                    hour += acc[i]*(2**i)
                mini = 0
                for i in range(6):
                    mini += acc[i+4]*(2**i)
                if 0<=hour<=11 and 0<=mini<=59:
                    ret.append('{}:{:02}'.format(hour,mini))
                return
            if left>10-begin: return
            for i in range(begin, 10):
                acc[i]=1
                traverse(i+1, left-1)
                acc[i]=0
        traverse(0,num)
        return ret

print(Solution().readBinaryWatch(2))

